#include <bits/stdc++.h>
// 2025/02/06
// tag: 
// Author: Zhang Muen
using namespace std;

using int64 = int64_t;

int64 n, len, s, h[500001], st[500001];

void push(int64 pos){
    while (st[len] < pos) 
        len--;
    st[++len] = pos;
}  

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> h[i];
    st[0] = LONG_LONG_MAX;
    push(h[1]);
    for (int64 i = 2; i <= n; i++) {
        int64 l = 0, r = len;
        while (l <= r){
            int64 mid = (l + r) / 2;
            if (st[mid] > h[i]) 
                l = mid + 1;
            else 
                r = mid - 1;
        }
        if (r == 0)
            s += len;
        else
            s += len - r + 1;
        push(h[i]);
    }
    cout << s << endl;
    return 0;
}